package algorithm.sort.array;

/**
 * @program: algorithm-data-structure
 * @description:
 * @author: Keyu Li
 * @create: 2021-08-30 14:16
 **/

public class SortMerge implements SortingMethod {
    String name = "Merge";

    @Override
    public String getName() {
        return name;
    }

    @Override
    public void sort(int[] arr) {
        sortRecursion(arr, 0, arr.length - 1);
    }

    private void sortRecursion(int[] arr, int start, int end) {
        if (start == end)
            return;
        sortRecursion(arr, start, (start + end) / 2);
        sortRecursion(arr, (start + end) / 2 + 1, end);
        merge(arr, start, end);
    }

    private void merge(int[] arr, int start, int end) {
        int length = end - start + 1;
        int leftLength = (end - start) / 2 + 1;
        int rightStart = start + leftLength;
        int rightLength = length - leftLength;
        int[] tempLeft = new int[leftLength + 1];
        int[] tempRight = new int[rightLength + 1];
        for (int i = 0; i < leftLength; i++) {
            tempLeft[i] = arr[start + i];
        }
        tempLeft[leftLength] = Integer.MAX_VALUE;
        for (int i = 0; i < rightLength; i++) {
            tempRight[i] = arr[rightStart + i];
        }
        tempRight[rightLength] = Integer.MAX_VALUE;

        int i, j, index;
        for (i = 0, j = 0, index = start; index <= end; index++) {
            if (tempLeft[i] <= tempRight[j])
                arr[index] = tempLeft[i++];
            else
                arr[index] = tempLeft[j++];

        }
    }
}

